package org.labuladong.动态规划算法.二维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-21:34
 * @Description:
 * @version: 1.0
 */
public class LC_122买卖股票的最佳时机III {

	//用一次遍历的方法来找到最大利润，而不需要使用动态规划
	public static int maxProfit(int[] prices) {
			int n = prices.length;
			int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
			int dp_pre_0 = 0; // 代表 dp[i-2][0]
			for (int i = 0; i < n; i++) {
				int temp = dp_i_0;
				dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
				dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
				dp_pre_0 = temp;
			}
			return dp_i_0;
		}

	public static void main(String[] args) {
		int[] prices = {7,1,5,3,6,4};
		System.out.println(maxProfit(prices));
	}
}
